
#ifndef __MEM_ALLOCA
#define __MEM_ALLOCA


/*
参考：  http://wiki.luajit.org/New-Garbage-Collector#GC-Algorithms

Arena： os分配1MB大小的内存。

定义block为16个字节大小（相当于4个int32）

则Arena中总共有64K个block（如不考虑metadata）

metadata：一个Arena 的头 1/64 空间（也即16K）被metadata占据。 16K的metadata需要管理约64K个block，即每个block可以占用2bit的metadata。我们只需要1bit来记录 是/否 分配出去就够了。

补丁：此文中的分配器，其API中的release是外部传入块的大小的。我们的release外部不传入大小。我们的解决方案是block不连续分配，这样release时把所有连续的mark清零即可。
*/


#define ARENA_SIZE (1024*1024)
#define BLOCK_SIZE 16
#define META_SIZE (1024*16)
#define BLOCK_NUMS (1024*63)


#define MAX_BLOCKS_ALLOCA (1024*4)

#ifndef FOR
#define FOR(M, N) for(int M=0;M<N;++M)
#endif


inline uint8_t __get_mask(int n){
	switch(n){
		case 0: return 0;
		case 1: return 0x01;
		case 2: return 0x03;
		case 3: return 0x07;
		case 4: return 0x0F;
		case 5: return 0x1F;
		case 6: return 0x3F;
		case 7: return 0x7F;
		case 8: return 0xFF;

		default: return 0xFF;
	}
}

inline void* makeArena(){
	void *p = ::malloc(ARENA_SIZE);
	memset(p, 0 , ARENA_SIZE);
	return p;
}

inline void freeArena(void* p){
	::free(p);
}

// alloca n blocks(not bytes) from given arena
inline void* myAlloca(void* arena, size_t n_block){
	if(NULL == arena || 0==n_block || n_block > MAX_BLOCKS_ALLOCA) return NULL;

	uint8_t *meta = (uint8_t*)arena;

	// fast mode first
	int n8 = n_block/8 + 1;		// for 8 blocks's meta is a char
	FOR(i, BLOCK_NUMS/8){
		if(0 == meta[i]){
			bool ok = true;
			for(int jj=1;jj<n8;++jj){
				if(0 != meta[i+jj]){
					ok = false;
					i = i+jj+1;		// optimization
					break;
				}
			}

			if(ok){
				// found enough free space. mark and return
				FOR(jj, n8-1){
					meta[i+jj] = 0xFF;
				}
				meta[i+n8-1] = __get_mask(n_block - (n8-1)*8);


				return (void*)(meta+META_SIZE + i*8*BLOCK_SIZE);
			}
		}
	}

	return NULL;
}

inline bool myCheckMem(void* arena, void *p){
	uint8_t *meta = (uint8_t*)arena;

	if((meta+META_SIZE)<=p && p<(meta+ARENA_SIZE)){
		return true;
	}

	return false;
}

inline void myDealloca(void* arena, void *p){
	uint8_t *meta = (uint8_t*)arena;
	uint8_t *pp = (uint8_t*)p;

	int begin = (pp - meta - META_SIZE) / BLOCK_SIZE / 8;
	for(int i=begin;i<BLOCK_NUMS/8;++i){
		if(0xFF != meta[i]){
			meta[i] = 0;
			break;
		}
		else{
			meta[i] = 0;
		}
	}
}


#endif
